#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>

struct ListNode {
    int val;
    struct ListNode* next;
};

struct ListNode* partition(struct ListNode* pHead, int x) {
    struct ListNode* list1 = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* list2 = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* cur = pHead;
    struct ListNode* tail1 = list1, * tail2= list2;
    while (cur) {
        if (cur->val < x) {
            tail1->next = cur;
            tail1 = tail1->next;
        }
        else {
            tail2->next = cur;
            tail2 = tail2->next;
        }
        cur = cur->next;
    }
    tail2->next = NULL;
    tail1->next = list2->next;
    return list1->next;
}

struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB) {
    int len1 = 0, len2 = 0;
    struct ListNode* cur1 = headA, * cur2 = headB;
    while (cur1) {
        len1++;
        cur1 = cur1->next;
    }
    while (cur2) {
        len2++;
        cur2 = cur2->next;
    }
    int len = abs(len1 - len2);
    cur1 = headA;
    cur2 = headB;
    if (len1 > len2) {
        while (len--) {
            cur1 = cur1->next;
        }
    }
    else {
        while (len--) {
            cur2 = cur2->next;
        }
    }
    while (cur1 != NULL && cur2 != NULL) {
        if (cur1 == cur2)
            return cur1;
        cur1 = cur1->next;
        cur2 = cur2->next;
    }
    return NULL;
}

bool hasCycle(struct ListNode* head) {
    struct ListNode* low = head, * fast = head;
    while (fast != NULL && fast->next != NULL) {
        low = low->next;
        fast = fast->next->next;
        if (low == fast)
            return true;
    }
    return false;
}

int main() {
    struct ListNode* n1 = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* n2 = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* n3 = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* n4 = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* n5 = (struct ListNode*)malloc(sizeof(struct ListNode));

    struct ListNode* N1 = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* N2 = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* N3 = (struct ListNode*)malloc(sizeof(struct ListNode));

    n1->val = 1;
    n2->val = 2;
    n3->val = 3;
    n4->val = 4;
    n5->val = 5;

    N1->val = 2;
    N2->val = 4;
    N3->val = 6;

    n1->next = n2;
    n2->next = n3;
    n3->next = n4;
    n4->next = n5;
    n5->next = NULL;

    N1->next = N2;
    N2->next = N3;
    N3->next = NULL;

    struct ListNode* cur = n1;

    //while (cur) {
    //    printf("%d->", cur->val);
    //    cur = cur->next;
    //}
    //printf("NULL\n");

    
    //struct ListNode* head = partition(n1, 3);
    //struct ListNode* head = getIntersectionNode(n1, N1);
    bool ans = hasCycle(n1);
    printf("%d\n", ans);

    //while (head) {
    //    printf("%d->", head->val);
    //    head = head->next;
    //}
    //printf("NULL\n");

    return 0;
}